<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from adt.tnf on 19 December 2010 -->

<TITLE>Abstract data types to be used in specifications - Bit Sets of Arbitrary Length</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM>
<A HREF="http://eli-project.sourceforge.net/">
<IMG SRC="gifs/elilogo.gif" BORDER=0>
</A>&nbsp;
</TD>
<TD WIDTH="25" VALIGN=BOTTOM>
<img src="gifs/empty.gif" WIDTH=25 HEIGHT=25>
</TD>
<TD ALIGN=LEFT WIDTH="475" VALIGN=BOTTOM>
<A HREF="index.html"><IMG SRC="gifs/title.png" BORDER=0></A>
</TD>
<!-- |DELETE FOR SOURCEFORGE LOGO|
<TD>
<a href="http://sourceforge.net/projects/eli-project">
<img
  src="http://sflogo.sourceforge.net/sflogo.php?group_id=70447&amp;type=13"
  width="120" height="30"
  alt="Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads"/>
</a>
</TD>
|DELETE FOR SOURCEFORGE LOGO| -->
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_1.html#SEC1">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<A HREF="mailto:eli-project-users@lists.sourceforge.net">
<IMG SRC="gifs/button_mail.gif" BORDER=0 ALIGN="left"></A>
<A HREF="index.html"><IMG SRC="gifs/home.gif" BORDER=0 ALIGN="right"></A>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>Abstract data types to be used in specifications</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_2.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_4.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<H1><A NAME="SEC3" HREF="adt_toc.html#SEC3">Bit Sets of Arbitrary Length</A></H1>
<A NAME="IDX78"></A>
<P>
This module implements operations on sets over elements which are
nonnegative numbers. The range of each set value is dynamically
adapted as required by the operations.
<P>
Storage for set values is allocated when needed.
The module implementation uses efficient dynamic storage allocation
of the <CODE>obstack</CODE>.
The module does not implement automatic garbage collection.
Storage used by one instance of this module can be deallocated completely,
or for each single set value.
<P>
Some set operations are provided in two versions:
The functional version allocates a new result value and leaves
its operands unchanged.
The imperative version modifies one of its operands to represent
the result of the operation. 
Note: In the imperative case, too, the result of the function call
rather than the operand
has to be used for subsequent accesses to the modified set value,
e. g. <CODE>s = AddElemToBitSet (x, s);</CODE> where s is a <CODE>BitSet</CODE>
variable.
<P>
The module does not have generic parameters.
It is used by writing
<PRE>
   $/Adt/BitSet.fw
</PRE>
in a <CODE>.specs</CODE> file.
<P>
All entities exported by this module can be used in specifications
of type <CODE>.lido</CODE>, <CODE>.init</CODE>, <CODE>.finl</CODE>, and <CODE>.con</CODE>.
They can also be used in <CODE>.pdl</CODE> specifications or in C modules 
if the interface file <CODE>BitSet.h</CODE> is imported there.
<P>
The module exports the following type names and macros:
<A NAME="IDX79"></A>
<A NAME="IDX80"></A>
<P>
<DL COMPACT>
<DT><CODE>BitSet</CODE>
<DD>   A pointer type representing sets.
<P>
<DT><CODE>NullBitSet</CODE>
<DD>   The 0 pointer representing an empty set.
   Note: The empty set can be represented in different ways.
   Hence, the function <CODE>EmptyBitSet</CODE> must be used to check
   for a set being empty.
<P>
</DL>
<P>
The following set processing functions are supplied by the module:
<A NAME="IDX81"></A>
<A NAME="IDX82"></A>
<A NAME="IDX83"></A>
<A NAME="IDX84"></A>
<A NAME="IDX85"></A>
<A NAME="IDX86"></A>
<A NAME="IDX87"></A>
<A NAME="IDX88"></A>
<A NAME="IDX89"></A>
<A NAME="IDX90"></A>
<A NAME="IDX91"></A>
<A NAME="IDX92"></A>
<A NAME="IDX93"></A>
<A NAME="IDX94"></A>
<A NAME="IDX95"></A>
<A NAME="IDX96"></A>
<A NAME="IDX97"></A>
<A NAME="IDX98"></A>
<A NAME="IDX99"></A>
<A NAME="IDX100"></A>
<A NAME="IDX101"></A>
<A NAME="IDX102"></A>
<A NAME="IDX103"></A>
<A NAME="IDX104"></A>
<P>
<DL COMPACT>
<DT><CODE>void FreeBitSet (BitSet s)</CODE>
<DD>Deallocates the set <CODE>s</CODE>.
<P>
<DT><CODE>void FreeMemBitSet (void)</CODE>
<DD>Deallocates all memory allocated for sets.
<P>
<DT><CODE>BitSet NewBitSet (void)</CODE>
<DD>Allocates an empty set.
<P>
<DT><CODE>int EqualBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Yields 1 if <CODE>s1</CODE> and <CODE>s2</CODE> contain the same elements; otherwise 0.
<P>
<DT><CODE>int EmptyBitSet (BitSet s)</CODE>
<DD>Yields 1 if <CODE>s</CODE> is empty; otherwise 0.
<P>
<DT><CODE>int EmptyIntersectBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Yields 1 if the intersection of <CODE>s1</CODE> and <CODE>s2</CODE> is empty; 
otherwise 0.
<P>
<DT><CODE>int ElemInBitSet (int el, BitSet s)</CODE>
<DD>Yields 1 if <CODE>el</CODE> is an element of <CODE>s</CODE>; otherwise 0.
<P>
<DT><CODE>int CardOfBitSet (BitSet s)</CODE>
<DD>Yields the number of elements in <CODE>s</CODE>.
<P>
<DT><CODE>BitSet AddElemToBitSet (int el, BitSet s)</CODE>
<DD>Imperative: Adds element <CODE>el</CODE> to set <CODE>s</CODE>.
<P>
<DT><CODE>BitSet ElemToBitSet (int el)</CODE>
<DD>Returns a set consisting only of element <CODE>el</CODE>. This function
can be used as the third (function) parameter in an application of
the <CODE>CONSTITUENTS</CODE> construct.
<P>
<DT><CODE>BitSet AddRangeToBitSet (int el1, int el2, BitSet s)</CODE>
<DD>Imperative: All elements in the range from <CODE>el1</CODE> to <CODE>el2</CODE> 
are added to the set <CODE>s</CODE>.
<P>
<DT><CODE>BitSet SubElemFromBitSet (int el, BitSet s)</CODE>
<DD>Imperative: Subtracts element <CODE>el</CODE> from set <CODE>s</CODE>.
<P>
<DT><CODE>BitSet UnionToBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Imperative: <CODE>s1</CODE> is set to the union of <CODE>s1</CODE> and <CODE>s2</CODE>
<P>
<DT><CODE>BitSet IntersectToBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Imperative: <CODE>s1</CODE> is set to the intersection of <CODE>s1</CODE> and <CODE>s2</CODE>.
<P>
<DT><CODE>BitSet SubtractFromBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Imperative: <CODE>s2</CODE> is subtracted from <CODE>s1</CODE>.
<P>
<DT><CODE>BitSet ComplToBitSet (int upb, BitSet s)</CODE>
<DD>Imperative: <CODE>s</CODE> is complemented with respect to the
range 0 .. <CODE>upb</CODE>;
no assumption can be made on elements larger than <CODE>upb</CODE> in <CODE>s</CODE>
<P>
<DT><CODE>BitSet UniteBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Functional: Yields the union of <CODE>s1</CODE> and <CODE>s2</CODE>
<P>
<DT><CODE>BitSet IntersectBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Functional: Yields the intersection of <CODE>s1</CODE> and <CODE>s2</CODE>
<P>
<DT><CODE>BitSet SubtractBitSet (BitSet s1, BitSet s2)</CODE>
<DD>Functional: Yields <CODE>s1</CODE> minus <CODE>s2</CODE>.
<P>
<DT><CODE>BitSet ComplBitSet (int upb, BitSet s)</CODE>
<DD>Functional: Yields the complement of <CODE>s</CODE> with respect to the
range 0 .. <CODE>upb</CODE>;
no assumption can be made on elements larger than <CODE>upb</CODE> in the result.
<P>
<DT><CODE>int NextElemInBitSet (int elem, BitSet s)</CODE>
<DD>Yields the smallest element of <CODE>s</CODE> that is larger than <CODE>elem</CODE>,
if any; -1 otherwise.
<P>
<DT><CODE>void ApplyToBitSet (BitSet s, void func(int))</CODE>
<DD>Applies the function <CODE>func</CODE> to each element of <CODE>s</CODE>
<P>
<DT><CODE>void PrintBitSet (BitSet s)</CODE>
<DD>Prints <CODE>s</CODE> as a string of 0 and 1 to <CODE>stdout</CODE>.
<P>
<DT><CODE>void PrintElemsBitSet (BitSet s)</CODE>
<DD>Prints <CODE>s</CODE> as a comma separated sequence of its 
elements to <CODE>stdout</CODE>.
</DL>
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_2.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_4.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>
